package bank;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class _21MergeTwoLists {
    public static ListNode20 mergeTwoLists(ListNode20 list1, ListNode20 list2) {
        //先判断空表
        if(list1 == null){
            return list2;
        }else if(list2 == null){
            return list1;
        }

        //有两个链表，需要把他们整合到一张链表上去
        //比较简单的思路是两个表分别遍历，获得的数据放到一个数组中去，排序后加入目标链表
        //但是这里采用更好的办法
        ListNode20 res = new ListNode20();
        ListNode20 p1 = list1,p2 = list2,p = res;
        while (p1!=null && p2!=null){
            //比较数据
            if(p1.val <= p2.val){
                //p1中val更小
                p.next = new ListNode20(p1.val);
                p = p.next;
                p1 = p1.next;
            }else {
                p.next = new ListNode20(p2.val);
                p = p.next;
                p2 = p2.next;
            }
            //退出循环的条件是其中一个工作指针为空
        }
        if(p1 == null){
            p.next = p2;
        }else if(p2 == null){
            p.next = p1;
        }
        return res.next;

    }

    public static class ListNode20{
        int val;
        ListNode20 next;

        ListNode20() {
        }

        ListNode20(int val) {
            this.val = val;
        }

        ListNode20(int val, ListNode20 next) {
            this.val = val;
            this.next = next;
        }
    }
}

